#ifndef HASHTABLE
#define HASHTABLE

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
enum class State
{
    DELETE,
    EMPTY,
    EXISTS
};

template <typename K, typename V>
struct HashData
{
    std::pair<K, V> _hashdata;
    State _state = State::EMPTY;
};

template <typename K>
struct HashFunc
{
    size_t operator()(const K &key)
    {
        return static_cast<size_t>(key);
    }
};

template <>
struct HashFunc<std::string>
{
    size_t operator()(const std::string &s) const
    {
        size_t h = 0;
        for (char ch : s)
        {
            h += ch - '0';
            h *= 131;
        }
        return h;
    }
};

inline unsigned long __stl_next_prime(unsigned long n)
{
    // Note: assumes long is at least 32 bits.
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291};
    const unsigned long *first = __stl_prime_list;
    const unsigned long *last = __stl_prime_list + __stl_num_primes;
    const unsigned long *pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

namespace open_address
{
    template <typename K, typename V, typename HashKey = HashFunc<K>>
    class HashTable
    {
        const State del = State::DELETE;
        const State emp = State::EMPTY;
        const State exi = State::EXISTS;

    public:
        HashTable() : _hash(__stl_next_prime(0)), _n(0)
        {
        }
        bool Insert(const std::pair<K, V> &kv)
        {
            if (Find(kv.first) != nullptr)
                return false;

            // 使用负载因子决定是否扩容
            if (_n * 10 / _hash.size() >= 7)
            {
                HashTable<K, V> ret;
                ret._hash.resize(std::move(__stl_next_prime(_hash.size() + 1)));
                for (auto ht : _hash)
                {
                    if (ht._state == exi)
                        ret.Insert(ht._hashdata);
                }
                _hash.swap(ret._hash);
            }

            size_t hash0 = kv.first % _hash.size();
            size_t hashi = hash0;
            size_t i = 1;
            int flag = 1;
            while (_hash[hashi]._state == exi)
            {
                hashi = (hash0 + i) % _hash.size();
                ++i;

                // 二次探测
                // hashi = (hash0 + i * i * flag) % _hash.size();
                // if (hashi < _hash.size())
                //     // flag会出现负数，hashi可能会变成负数，修正下标
                //     hashi += _hash.size();

                // // 左右两边找一个适合插入的位置，所以++i写在else内部
                // if (flag == 1)
                //     flag = -1;
                // else
                // {
                //     ++i;
                //     flag = 1;
                // }
            }
            _hash[hashi]._hashdata = kv;
            _hash[hashi]._state = exi;
            ++_n;

            return true;
        }

        HashData<K, V> *Find(const K &key)
        {
            size_t hash0 = key % _hash.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_hash[hashi]._state != emp)
            {
                if (_hash[hashi]._state == exi && _hash[hashi]._hashdata.first == key)
                {
                    return &_hash[hashi];
                }
                hashi = (hash0 + i) % _hash.size();
                ++i;
            }
            return nullptr;
        }

        bool Erase(const K &key)
        {
            HashData<K, V> *ret = Find(key);
            if (ret == nullptr)
                return false;
            else
            {
                ret->_state = del;
                return true;
            }
        }
        bool Empty()
        {
            return _n == 0;
        }

        int Size()
        {
            return _n;
        }
        // ~HashTable(){}
    private:
        std::vector<HashData<K, V>> _hash;
        size_t _n;
    };
}

// 哈希桶，对应位置下面挂一个链表
namespace hash_bucket
{
    template <typename T>
    struct HashNode
    {
        T _data;
        HashNode<T> *_next;

        HashNode(const T &data)
            : _data(data),
              _next(nullptr)
        {
        }
    };

    template <typename K, typename T, typename HashKey, typename KeyOfT>
    class HashTable;

    template <typename K, typename T, typename Ref, typename Ptr, typename HashKey, typename KeyOfT>
    struct HashIterator
    {
        using Node = HashNode<T>;
        using ht = HashTable<K, T, HashKey, KeyOfT>;
        using Self = HashIterator<K, T, Ref, Ptr, HashKey, KeyOfT>;

        Node *_node;
        const ht *_table;

    public:
        HashIterator(Node *node, const ht *table)
            : _node(node),
              _table(table)
        {
        }

        Ref operator*() const
        {
            return _node->_data;
        }

        Ptr operator->() const
        {
            return &_node->_data;
        }

        bool operator!=(const Self &other) const
        {
            return _node != other._node;
        }

        Self &operator++()
        {
            if (_node == nullptr)
                return *this;

            if (_node->_next)
                _node = _node->_next;
            else
            {
                KeyOfT kot;
                HashKey hashkey;
                size_t hash0 = hashkey(kot(_node->_data)) % _table->TableSize();
                ++hash0;

                while (hash0 < _table->TableSize())
                {
                    _node = _table->GetTable()[hash0];

                    if (_node)
                        break;
                    else
                        ++hash0;
                }

                if (hash0 == _table->TableSize())
                    _node = nullptr;
            }
            return *this;
        }

        Self operator++(int)
        {
            Self *temp = *this;
            ++(*this);
            return temp;
        }
    };

    template <typename K, typename T, typename Ref, typename Ptr, typename HashKey, typename KeyOfT>
    struct HashIterator;

    template <typename K, typename T, typename HashKey = HashFunc<K>, typename KeyOfT>
    class HashTable
    {

        using Node = HashNode<T>;

    public:
        const std::vector<Node *> &GetTable() const { return _tables; }
        size_t TableSize() const { return _tables.size(); }

        using Iterator = HashIterator<K, T, T &, T *, HashKey, KeyOfT>;
        using ConstIterator = HashIterator<K, T, const T &, const T *, HashKey, KeyOfT>;
        HashTable() : _tables(__stl_next_prime(0)), _n(0) {}

        Iterator Begin()
        {
            if (_n == 0)
                return End();
            // 返回第一个非空的桶的第一个节点
            for (int i = 0; i < _tables.size(); i++)
            {
                if (_tables[i] != nullptr)
                    return Iterator(_tables[i], this);
            }
            return End();
        }

        Iterator End()
        {
            return Iterator(nullptr, this);
        }

        ConstIterator Begin() const
        {
            if (_n == 0)
                return End();
            // 返回第一个非空的桶的第一个节点
            for (int i = 0; i < _tables.size(); i++)
            {
                if (_tables[i] != nullptr)
                    return ConstIterator(_tables[i], this);
            }
            return End();
        }

        ConstIterator End() const
        {
            return ConstIterator(nullptr, this);
        }

        std::pair<Iterator, bool> Insert(const T &data)
        {
            // 负载因子等于1时扩容

            KeyOfT kot;
            HashKey hashkey;

            Iterator it = Find(kot(data));

            if (it != End())
                return {it, false};

            if (_n == _tables.size())
            {
                // HashTable<K, V> newht;
                // newht._tables.resize((_n << 1));
                // for (size_t i = 0; i < _tables.size(); i++)
                // {
                //     Node *cur = _tables[i];
                //     while (cur)
                //     {
                //         newht.Insert(cur->_kv);
                //         cur = cur->_next;
                //     }
                // }
                // _tables.swap(newht._tables);

                size_t len = _n << 1;
                std::vector<Node *> newTable(len);

                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node *cur = _tables[i];
                    while (cur)
                    {
                        Node *next = cur->_next;
                        size_t hash0 = hashkey((kot(cur->_data))) % len;
                        cur->_next = newTable[hash0];

                        newTable[hash0] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }

                _tables.swap(newTable);
            }

            size_t hash0 = hashkey(kot(data)) % _tables.size();
            Node *newnode = new Node(data);
            newnode->_next = _tables[hash0];
            _tables[hash0] = newnode;

            ++_n;

            return {Iterator(newnode, this), true};
        }

        Iterator Find(const K &key)
        {
            HashKey hashkey;
            KeyOfT kot;
            size_t hash0 = hashkey(key) % _tables.size();
            Node *cur = _tables[hash0];
            while (cur)
            {
                if (kot(cur->_data) == key)
                    return Iterator(cur, this);
                cur = cur->_next;
            }

            return End();
        }

        bool Erase(const K &key)
        {
            KeyOfT kot;
            HashKey hashkey;
            size_t hash0 = hashkey(key) % _tables.size();
            Node *cur = _tables[hash0];
            Node *prev = nullptr;
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    if (prev == nullptr)
                        _tables[hash0] = cur->_next;
                    else
                        prev->_next = cur->_next;

                    delete cur;
                    --_n;
                    return true;
                }

                prev = cur;
                cur = cur->_next;
            }
            return false;
        }

        bool Empty()
        {
            return _n == 0;
        }

        int Size()
        {
            return _n;
        }

        ~HashTable()
        {
            for (int i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                while (cur)
                {
                    Node *next = cur->_next;
                    delete cur;
                    --_n;

                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }

    private:
        std::vector<Node *> _tables;
        size_t _n = 0;
    };
}

#endif